package test230606;

import java.util.Arrays;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/6 0:59
 * 673. 最长递增子序列的个数
 * https://leetcode.cn/problems/number-of-longest-increasing-subsequence/
 */
public class Solution03 {

    public int findNumberOfLIS(int[] nums) {
        // 边界处理
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] len = new int[n];  // len[i] 表示以 i 位置结尾的所有子序列的最大长度
        int[] count = new int[n];  // count[i] 表示以 i 位置结尾的所有长度最大的子序列的个数
        int maxLen = 1;  // 记录最长递增子序列长度
        Arrays.fill(len, 1);  // 最短长度为 1
        Arrays.fill(count, 1);  // 最少个数为 1
        // 动态规划过程
        int retLen = 1, retCount = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j <= i - 1; ++j) {
                if (nums[i] > nums[j]) {
                    if (len[j] + 1 == len[i]) {
                        count[i] += count[j];
                    } else if (len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }
            if (retLen == len[i]) {
                retCount += count[i];
            } else if (retLen < len[i]) {
                retLen = len[i];
                retCount = count[i];
            }
        }
        return retCount;
    }
}
